package 练习;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : 最长递增子序列
 * 功能概要  :
 *
 * @author yangwk
 * @date 2024/9/11 14:33
 */
public class 最长递增子序列 {
    public static void main(String[] args) {
        System.out.println(maxAscLengthDp(new int[]{0,1,0,3,2,3}));
        System.out.println(maxAscLength(new int[]{0,1,0,3,2,3}));
    }
    public static int maxAscLengthDp(int[] arr) {
        int length = arr.length;
        int[] dp = new int[length];
        int max = 1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                } else if (arr[i] == arr[j]) {
                    dp[i] = Math.max(dp[j], dp[i]);
                }
                max = Math.max(dp[i], max);
            }
        }
        return max;
    }

    public static int maxAscLength(int[] arr) {
        List<Integer> ascList = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int ele = arr[i];
            int index = binarySearch(ascList.toArray(new Integer[ascList.size()]), ele);
            if (index > ascList.size() - 1) {
                ascList.add(ele);
            } else {
                ascList.set(index, ele);
            }

        }
        return ascList.size();
    }

    public static int binarySearch(Integer[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int middle = (left + right) / 2;
            if (arr[middle] == target) {
                return middle;
            } else if (arr[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        return left;
    }
}
